//题目:
// 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
// 环形数组 意味着数组的末端将会与开头相连呈环状。
// 形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
// 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。
// 形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
#include<iostream>
#include<limits.h>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        //题意转换：本题可分为两类：①最大连续子数组和不是收尾相连的  ②是收尾相连的
        //对于①，相当于取环；对于②，反着去求，即求最小连续子数组和，用sum-min_val即结果

        //1.创建dp细化表
        int n=nums.size();
        vector<int> f(n);//f[i]表示以第i个位置为结尾的最大连续子数组和
        vector<int> g(n);//g[i]表示以第i个位置为结尾的最小连续子数组和
        //2.初始化
        f[0]=nums[0],g[0]=nums[0];
        //3.填表————动态转移方程：f[i]=nums[i]+max(0,nums[i-1]); g[i]=nums[i]+min(0,nums[i-1]);
        int sum=nums[0],min_val=g[0];
        for(int i=1;i<n;i++)
        {
            f[i]=nums[i]+max(0,f[i-1]); 
            g[i]=nums[i]+min(0,g[i-1]);
            sum+=nums[i],min_val=min(min_val,g[i]);
        }
        //4.确定返回值
        int ret=sum-min_val==0?INT_MIN:sum-min_val;//第②中情况所得到的最大值，即首尾相连时最大连续子数组和
        //处理特殊情况：若sum==min_val，说明该数组全是负数，此时ret不属于第②中情况，而是第一种
        for(int i=0;i<n;i++)
            ret=max(ret,f[i]);
        return ret;
    }
};